/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LianBao
 * Date: 2024-11-16
 * Time: 21:46
 */
public class Main {

    public int hammingDistance(int x, int y) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (((x >> i) & 1) != ((y >> i) & 1)) {
                count++;
            }
        }
        return count;
    }

    public int[] countBits(int n) {
        int[] ret = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            ret[i] = countOne(i);
        }
        return ret;
    }

    // 计算n的二进制表示中1的个数
    public int countOne(int n) {
        int count = 0;
        // for (int i = 0; i < 32; i++) {
        //     if (((n >> i) & 1) == 1) {
        //         count++;
        //     }
        // }
        // 优化:
        while (n > 0) {
            n &= (n - 1);//n & (n-1)每次都能干掉最右边的1,只需要看这个循环执行了多少次,1就有多少个
            count++;
        }
        return count;
    }

    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (((n >> i) & 1) == 1) {
                count++;
            }
        }
        return count;
    }

    public int singleNumber(int[] nums) {
        int ret = nums[0];
        for (int i = 1; i < nums.length; i++) {
            ret ^= nums[i];
        }
        return ret;
    }

    public int[] singleNumber3(int[] nums) {
        int ret = 0;
        int[] ans = new int[2];
        ans[0] = 0;
        ans[1] = 0;
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
        }
        //此时,只出现一次的这两个数的异或结果就是ret
        //取出ret最右边的1,假设是第x位
        int lowBit = ret & (-ret);
        //把数组分为两类,一类是第x位为0,另一类是第x位为1
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & lowBit) != 0) {
                ans[0] ^= nums[i];
            } else {
                ans[1] ^= nums[i];
            }
        }
        return ans;
    }


    public boolean isUnique(String astr) {
        int BitMap = 0;
        int n = astr.length();
        if (n > 26) {
            return false;
        }
        for (int i = 0; i < n; i++) {
            char ch = astr.charAt(i);

            if (((BitMap >> (ch - 'a')) & 1) == 1) {
                return false;
            } else {
                BitMap |= (1 << (ch - 'a'));
            }
        }
        return true;
    }

    public int missingNumber(int[] nums) {
        // 异或运算
        int n = nums.length;
        int ret = 0;
        for (int i = 0; i <= n; i++) {
            ret ^= i;
        }
        for (int i = 0; i < n; i++) {
            ret ^= nums[i];
        }
        return ret;

        // int n = nums.length;
        // //高斯求和
        // int sum = ((n)*(n+1))/2;
        // int numsSum = 0;
        // for(int i=0;i<nums.length;i++) {
        // numsSum += nums[i];
        // }
        // return sum - numsSum;
    }

    public int getSum(int a, int b) {
        while (b != 0) {
            int x = a ^ b;//先计算无进位相加
            int carry = (a & b) << 1;
            a = x;
            b = carry;
        }
        return a;
    }


    public int singleNumber2(int[] nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {//依次修改ret中的每一位
            int sum = 0;
            for (int j = 0; j < nums.length; j++) {
                sum += ((nums[j] >> i) & 1);//计算第i位的和
            }
            sum %= 3;
            if (sum == 1) {
                //修改第i位置的值
                ret |= (1 << i);
            }
        }
        return ret;
    }


    public int[] missingTwo(int[] nums) {
        int len = nums.length;
        int N = len + 2;
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
        }
        for (int i = 1; i <= N; i++) {
            ret ^= i;
        }
        // ret为消失的两个数^的结果
        int lowBit = ret & (-ret);
        int[] ans = new int[2];
        ans[0] = 0;
        ans[1] = 0;
        for (int i = 1; i <= N; i++) {
            if ((i & lowBit) != 0) {
                ans[0] ^= i;
            } else {
                ans[1] ^= i;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & lowBit) != 0) {
                ans[0] ^= nums[i];
            } else {
                ans[1] ^= nums[i];
            }
        }
        return ans;
    }


}
